perm filename OUT[NCC,BGB] blob
sn#143274 filedate 1975-02-06 generic text, type T, neo UTF8
{F1;F2;F3;⊂C;<N;αWINGED EDGE.;λ30;P1;I125,0;JC;FA}
{JC;FD} A POLYHEDRON REPRESENTATION FOR COMPUTER VISION
{λ15;FA} Author: {JCFC} Bruce G. Baumgart
{FA} Author's Address: {JC} Stanford Artificial Intelligence Laboratory
{JC} Stanford University
{JC} Stanford, California 94305
{JC} for the National Computer Conference
{JC} Session on Graphic Models of Physical Systems
{JC} Session chaired by Charles M. Eastman
{λ10;W250;JA;FA}
1. Use of Polyhedra in Computer Vision.
2. Introduction to the Winged Edge.
3. Sequential Accessing.
4. Perimeter Accessing.
5. Basic Polyhedron Synthesis.
6. Edge and Face Splitting.
7. Conclusion.
8. References.
{λ30;W0;I1000,0;JU}
⊂1. Use of Polyhedra in Computer Vision.⊃
My approach to computer vision is best characterized as
inverse computer graphics. In computer graphics, the world is
represented in sufficient detail so that the image forming process
can be numerically simulated to generate synthetic television images;
in the inverse, perceived television pictures (from a real TV camera)
are analysed to compute detailed geometric models. For example, the
polyhedron in Figure 1 was computed from views of a plastic horse on
a turntable. It is hoped, that visually acquired 3-D geometric models
can be of use to other robotic processes such as manipulation,
navigation or recognition.
Once acquired, a 3-D model can be used to anticipate the
appearance of an object in a scene, making feasible a quantitative
form of visual feedback. In Figure 2 for example, the approximate
video appearance of the machine parts schematically depicted (top)
can be computed and analyzed for edges (middle) and compared with an
edge analysis of an actual video image of the parts (bottom). By
comparing the predicted image with a perceived image, the
correspondence between features of the internal model and features of
the external reality can be established and a corrected location of
the parts and the camera can be measured.
An example of a purely descriptive vision technique is the
silhouette cone intersection method, which is a conceptually simple
form of wide angle stereo reconstruction. The idea arose out of an
original intention to do "blob" oriented visual model acquisition,
however a 2-D blob came to be represented by a silhouette polygon and
a 3-D blob consequently came to be represented by a polyhedron. The
present implementation requires a very favorably arranged viewing
environment (white objects on dark backgrounds or vice versa);
application to more natural situations might be possible if the
necessary hardware (and software) were available for extracting depth
discontinuities by bulk correlation. Furthermore, the restriction to
turntable rotation is for the sake of easy camera solving; this
restriction could be lifted by providing stronger feature tracking
for camera calibration.
Like in the joke about carving a statue by cutting away
everything that does not look like the subject, the approximate shape
of the horse is hewed out of 3-D space by cutting away everything
that falls outside of the silhouettes. The example of silhouette cone
intersection depicted in Figure 1; the model was made from three
silhouettes of the horse facing to the left which may be compared
with a video image and a final view of the result of the horse facing
to the right - a backside consistent with the front views
was automatically constructed by the process.
The silhouette cone intersection method can construct concave
objects and even objects with holes in them - what are missed are
concavities with a full rim, that is points on the surface of the
object whose tangent plane cuts the surface in a loop that encloses
the point.
Unfortunately, the above approachs to computer vision (both
verification vision and descriptive vision) are only as strong as the
state of the art in 3-D computer graphics. Accordingly my recent
vision work has almost entirely been a quest for better ways to
represent and manipulate 3-D objects. Restricting the problem to
representing solid, opaque, rigid 3-D objects only a very few
significantly different geometric modeling ideas are known: arrays,
3-D density functions, 2-D parametric functions, volume elements,
cross sectional elements, skeletons, manifolds and polyhedra; of which
I have concentrated on polyhedra because they are simple enough to
readily handle in a computer and complex enough to represent an
arbitrary opaque surface. Accordingly the rest of this paper is
devoted to presenting a particular polyhedron representation for
which convenient sets of manipulation routines have been developed.
⊂2. Introduction to the Winged Edge.⊃
The Winged Edge polyhedron representation is implemented as a
data structure composed of small blocks of words containing pointers
and data in the fashion usual to graphics and simulation. An
introduction to such data structures can be found in Chapter 2 of
Knuth's Art of Computer Programming [Knuth 1968]. Quickly reviewing
Knuth's terminology, a node is a group of consecutive words of
memory, a field is a named portion of a node and a link is the
machine address of a node. The notation for referring to a field of
a node consists simply of the field name followed by a link
expression enclosed in parentheses. For example, the two faces of an
edge node whose link is stored in the variable named "edge", are
found in the fields named NFACE and PFACE, and are referred to as
NFACE(edge) and PFACE(edge). Although my latest language of
implementation is PDP-10 machine code, examples will be given in a
fictional programming language which combines ALGOL with Knuth's
node/link notation.
{H7;O0,630,700;
L0,-20,0*5,-61*5;L0,20,0*5,61*5;
L-86*5,83*5,0*5,61*5,86*5,83*5;L-86*5,-83*5,0*5,-61*5,86*5,-83*5;
H2;
L42*5,106*5,86*5,83*5,126*5,0*5,86*5,-83*5,42*5,-106*5,-42*5,-106*5;
L-42*5,-106*5,-86*5,-83*5,-126*5,0*5,-86*5,83*5,-42*5,106*5,42*5,106*5;
L-30,-10;FB }edge
{L-380,-10; }NFACE(edge)
{L240,-10; }PFACE(edge)
{L-70,-370; }NVT(edge)
{L-70,350; }PVT(edge)
{L-360,320; }NCCW(edge)
{L-390,-360; }NCW(edge)
{L220,320; }PCW(edge)
{L260,-360; }PCCW(edge)
{I1300,0;O0,630,950;
λ10;JC;FA} ⊂FIGURE 1 - Winged Edge Topology.⊃
The orientation of links is as viewed from the exterior side of the surface.
The eight mnemonics in the figure, were derived as follows:
NFACE(edge) Negative Face of edge.
PFACE(edge) Positive Face of edge.
PVT(edge) Positive Vertex of edge.
NVT(edge) Negative Vertex of edge.
NCW(edge) edge in Negative face Clockwise from edge.
PCW(edge) edge in Positive face Clockwise from edge.
NCCW(edge) edge in Negative face Counter Clockwise from edge.
PCCW(edge) edge in Positive face Counter Clockwise from edge.{λ30;FA}
{Q}
A polyhedron in made up of four kinds of nodes: bodies,
faces, edges and vertices. The body node is the head of three rings:
a ring of faces, a ring of edges and a ring of vertices. In this
context, a ring is a doubly linked circular list with a head node.
Each face and each vertex points directly at only one of the edges on
its perimeter. Each edge points at its two faces and its two
vertices. Completing the topology, each edge node contains a link to
each of its four immediate neighboring edges clockwise and counter
clockwise about its face perimeters as seen from the exterior side of
the surface of the polyhedron. These last four links are the wings of
the edge, which provide the basis for efficient face perimeter and
vertex perimeter accessing. Finally, the links of the edge nodes
can be consistently oriented with respect to the surface of the
polyhedron so that the surface always has two sides: the inside and
the outside.
{|;λ10;JA}
BOX 1 {JC} WINGED EDGE STRUCTURES AND LINK NAMES.
~Data Structures~ ~Link Names~
1. Face Ring of a Body. NFACE PFACE
2. Edge Ring of a Body. NED PED
3. Vertex Ring of a Body. NVT PVT
4. First Edge of a Vertex. PED
5. First Edge of a Face. PED
6. The two faces of an edge: NFACE PFACE
7. The two vertices of an edge: NVT PVT
8. The four wing edges of an edge: NCW PCW NCCW PCCW
{|;λ30;JU}
Observe that there are twenty-two link fields in the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten links. If we allow a link name such as PED
to serve different roles depending on whether it applies to a body,
face, edge or vertex; then the minimum number of different link field
names that need to be coined is ten. The data structures and the link
fields comprising the structures are listed in Box 1. The
ten link names include: NFACE and PFACE for two fields that contain
face links in edges and the face ring, NED and PED for two fields
that contain edge links, NVT and PVT for two fields that contain
vertex links, and NCW, PCW, NCCW and PCCW for the four fields that
contain edge links and are called the wings.
By constraining the arrangement of links in an edge node both
the surface orientation (interior and exterior) and a linear
orientation of the edge as a directed vector can be encoded. Figure
1 diagrams the arrangement of the links comprising the topology of
an edge of a polyhedron as viewed from the exterior side of its
surface. Although the vertices in Figure 1 are shown with only
three edges, vertices may have any number of edges; the other
potential edges would not be directly linked to the middle edge of
the figure and so were not shown.
To complete the representation, space is allocated to contain
the 3-D coordinates of each vertex in fields named XWC, YWC and ZWC;
the initials "WC" stand for <World Coordinates>. For the sake of
vision and display, three more words are allocated to hold
the <Perspective Projected coordinates> of each vertex in fields
named XPP, YPP and ZPP. Also a word of thirty six status bits is
carried in every node: permanent status bits specify the type (body,
face, edge, vertex, etc.) of every node, temporary bits provide
space for operations such as hidden line elimination that require
marking. Passing now from necessities to conveniences, faces carry
exterior pointing normal vectors and several words of photometric
surface characteristics. The face vectors are derived from surface
topology and vertex loci, and so they are not basic geometric data
as in some representations. Bodies carry a print name, as well as
four link fields (DAD, SON, BRO, SIS) for implementing a parts tree
data structure; and two link fields (CW and CCW) for a body ring of
all the bodies in the world model. Node formats are given in Box 2
for an implementation based on fixed sized (twelve word) nodes.
The Winged Edge Polyhedron Representation as just presented
is complete. Edge nodes carry most of the topology, vertex nodes
carry the geometry, face nodes carry the photometry and body nodes
carry the nomenclature and parts tree structure. The point that
remains to be demonstrated, is that the appropriate subroutines for
creating, maintaining and exploiting edge orientation execute
efficiently and provide good primitives for solving such geometric
problems as hidden line elimination and polyhedral intersection.
{Q;P6;}⊂3. Sequential Accessing.⊃
An immediate consequence of the ring structures is that the
faces, edges and vertices of a body are sequentially accessible in the
manner illustrated by the following lines of code:
{JA;W0;λ7;F3}
COMMENT APPLY A FUNCTION TO ALL THE FACES, EDGES AND VERTICES OF A BODY;
PROCEDURE APPLY (PROCEDURE FN; INTEGER B);
BEGIN
INTEGER F,E,V;
F ← B; WHILE B≠(F←PFACE(F)) DO FN(F); COMMENT APPLY FUNCTION TO FACES OF A BODY;
E ← B; WHILE B≠(E←PED(E)) DO FN(E); COMMENT APPLY FUNCTION TO EDGES OF A BODY;
V ← B; WHILE B≠(V←PVT(V)) DO FN(V); COMMENT APPLY FUNCTION TO VERTICES OF A BODY;
END;
{JUFA;W0;λ30;}
\The rings could of course have been traversed in the other direction by
invoking NVT, NED and NFACE in place of PVT, PED and PFACE. The reason
for doubly linked lists (i.e. rings) is rapid deletion. Finally, observe
that the face and vertex rings could be eliminated at the cost of having
a more complicated face/vertex sequential accessing method requiring a
visitation marking bit in the status word of face and vertex nodes.
⊂4. Perimeter Accessing.⊃
The perimeter of a face is an ordered list of edges and
vertices, the perimeter of a vertex is an ordered list of edges and
faces, and the perimeter of an edge is an ordered list consisting of
exactly two faces and two vertices. The perimeter definitions are
caricatured in Figure 2. One virtue of the winged edge
representation is that both vertex and face perimeters can be
traversed in either direction (clockwise or counter clockwise) while
being dynamically maintained in "<one ring>".
{O0,630,350;L0,0;H3;FD
L0,-137;C6;L0,-137,0,170;C6;
L-44,10;FD}EDGE{
L-125,-170;FA}An Edge is surrounded{
L-120,-200;FA}by Faces and Vertices{
L0,200;JC;FC} FIGURE 2 - Three Kinds of Perimeters.{
L420,170,420-161,52;C6;
L420-161,52,420-100,-137;C6;
L420-100,-137,420+100,-137;C6;
L420+100,-137,420+161,52;C6;
L420+161,52,420,170;C6;
L420-45,-10;FD}FACE{
L420-125,-170;FA}A Face is surrounded{
L420-130,-200;FA}by Edges and Vertices{
L-420,0,-420-161,52;
L-420,0,-420-100,-137;
L-420,0,-420+100,-137;
L-420,0,-420+161,52;
L-420,170,-420,0;C6;
L-420-70,30;FD}VERTEX{
L-420-125,-170;FA}A Vertex is surrounded{
L-420-115,-200;FA}by Edges and Faces{O0,630,950;I590,0;JUFA}
Given one edge of a face (or vertex) perimeter, the next
edge clockwise (or counter clockwise) from the given edge about the
particular face (or vertex) can be retrieved from the data structure
with the assistance of two subroutines called ECW and ECCW. The idea
of the edge clocking routines is to match the given face (or vertex)
with one of the faces (or vertices) of the given edge and to then
return the appropriate wing. A possible coding of ECCW and ECW might
be as follows:
{↓;JA;λ7;F3}
COMMENT FETCH EDGE CCW FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
IF PFACE(E)=FV THEN RETURN(PCCW(E));
IF NFACE(E)=FV THEN RETURN(NCCW(E));
IF PVT(E)=FV THEN RETURN(PCW(E));
IF NVT(E)=FV THEN RETURN(NCW(E));
FATAL;
END "ECCW";
{↑;W670;JA;λ7;F3}
COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
IF PFACE(E)=FV THEN RETURN(PCW(E));
IF NFACE(E)=FV THEN RETURN(NCW(E));
IF PVT(E)=FV THEN RETURN(NCCW(E));
IF NVT(E)=FV THEN RETURN(PCCW(E));
FATAL;
END "ECW";
{W0;JUFA;λ30;}
\The first edge of a face or vertex is (of course) immediately
available from the PED field of the face or vertex. For example, the
two procedures below can be used to visit all the edges of a face or
all the edges of a vertex, respectively.
{JA;↓;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A FACE;
PROCEDURE APPLY (PROCEDURE FN; INTEGER F);
BEGIN
INTEGER E,E0;
E←E0←PED(F);
DO FN(E) UNTIL E0=(E←ECCW(E,F));
END;
{↑;W670;JA;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A VERTEX;
PROCEDURE APPLY (PROCEDURE FN; INTEGER V);
BEGIN
INTEGER E,E0;
E←E0←PED(V);
DO FN(E) UNTIL E0=(E←ECCW(E,V));
END;
{JUFA;W0;λ30;}
Using the same idea as in the edge clocking routines, a face
or vertex can be retrieved relative to a given edge and a given face
or vertex. These routines include: FCW and FCCW which return the face
clockwise or counter clockwise from a given edge with respect to a
given vertex; VCW and VCCW which return the vertex clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which returns the face or vertex of the given edge opposite the
given face or vertex. Together the seven routines: ECW, ECCW, VCW,
VCCW, FCW, FCCW and OTHER exhaust the possible oriented retrievals
from an edge node; they also alleviate the need to ever explicitly
reference a wing field when traveling the surface of a polyhedron.
With node type checking the primitives can be made stronger, for example
ECCW(vertex,face) is implemented to return the edge counter clockwise
from the given vertex about the given face.
With node type checking and signed arguments the seven perimeter
accessing routines could even be replaced by a single routine perhaps
named PERIMETER_FETCH or PGET. On the other hand, I favor having the
proliferation of accessing names for the sake of documenting the
clocking direction and the types of nodes involved.
Two remaining accessing routines, of minor importance,
are BGET(entity) and LINKED(entity,entity). BGET of a face, edge or
vertex merely cycles the appropriate ring to retrieve the body of the
given entity. The LINKED routine determines whether its two
arguments (faces, edges or vertices) are adjacent; there are six
LINKED cases: (i) Face-Face, returns a common edge or FALSE; (ii)
Face-Edge, returns boolean value F=PFACE(E) ∨ F=NFACE(E); (iii)
Edge-Edge, returns a common vertex or false; (v) Edge-Vertex,
returns boolean value V=PVT(E) ∨ V=NVT(E); (vi) Vertex-Vertex,
returns common edge or FALSE. (As in LISP, zero is false and non-zero
is true).
⊂5. Basic Polyhedron Synthesis.⊃
{|;λ10;JA}
BOX 3 {JC} LOWEST LEVEL WINGED EDGE ROUTINES.
<Node Makers:> MKNODE, MKB, MKF, MKE, MKV, MKTRAM.
<Node Killers:> KLNODE, KLB, KLF, KLE, KLV.
<Wing Mungers:> WING, INVERT, EVERT.
<Surface Fetchers:> ECW, ECCW, OTHER, VCW, VCCW, FCW, FCCW, LINKED.
<Parts Tree Routines:> BDET, BATT, BGET.
{|;λ30;JU}
There are sixteen routines for node creation and link
manipulation which when combined with the nine accessing routines of
the previous section form the nucleus of a polyhedron modeling
system. These routines are very low level in that the final
applications user of winged polyhedra will never explicitly need to
make a node or mung a link. The word <mung> (meaning to modify an
existing structure by altering links in place) is LISP slang that
deserves to be promoted into the technical jargon; traditionally, a
mung routine is one which makes applications of the LISP primitives
RPLACA and RPLACD. The twenty five routines listed in Box 3 are the
bedrock for the Euler primitives, which are an elegant set of
subroutines for altering polyhedra while always maintaining the Euler
relation: F-E+V=2*B-2*H between the numbers of bodies, faces, edges,
vertices and handles. Examples of Euler primitives are given in
another paper written for this conference [Eastman, Lividini & Stoker
1975] as well as Section 3 of [Baumgart 1974B]; and so will not need
to be further discussed.
<Node Makers and Killers>. The MKNODE and KLNODE are the raw
storage allocation routines which fetch or return a node from the
available free storage. The MKB routine creates a body node with
empty face, edge and vertex rings; the body is placed into the body
ring of the world model. The MKF, MKE and MKV each take one argument
and create a new face, edge or vertex node in the ring of the given
entity; with type checking these three primitives could be
consolidated. Finally the MKTRAM node creates a <tram node>, which
consists of twelve real numbers that represent either a Euclidean
transformation or a Cartesian frame of reference depending on the
context. As a cartesian frame of reference the tram node is
interpreted as a 3-D locus in world coordinates with a right handed
triad of orthogonal unit vectors; as a Euclidean transformation the
tram node is interpreted as a translation vector followed by a
rotation matrix. Tram nodes are further explained in [Baumgart
1974B]. The corresponding kill routines KLB, KLF, KLE and KLV remove
the entity from its respective ring and return its node to free
storage.
<Wing Mungers>. The WING(edge1,edge2) routine finds which
face and vertex the arguments edge1 and edge2 have in common and
stores the wing pointers between edge1 and edge2 accordingly; the
exact link manipulations are illustrated in the example coding of
the WING procedure immediately following this paragraph. Recalling
that edges are directed vectors, the INVERT(E) routine flips the
direction of an edge by swapping the contents of the appropriate
fields as follows: PFACE(E)↔NFACE(E); PVT(E)↔NVT(E); NCW(E)↔NCCW(E)
and PCW(E)↔PCCW(E). Finally, the EVERT(B) routine
turns a body inside out, by
performing the following link swaps on all the edges of the given body:
PFACE(E)↔NFACE(E); NCW(E)↔PCCW(E); and NCCW(E)↔PCW(E).
{JA;λ7;F3;W120,1260,0,1900;}
PROCEDURE WING(INTEGER E1,E2);
BEGIN
IF PVT(E1)=PVT(E2)∧PFACE(E1)=NFACE(E2)THEN BEGIN PCW(E1)←E2;NCCW(E2)←E1;END;
IF PVT(E1)=PVT(E2)∧NFACE(E1)=PFACE(E2)THEN BEGIN NCCW(E1)←E2; PCW(E2)←E1;END;
IF PVT(E1)=NVT(E2)∧PFACE(E1)=PFACE(E2)THEN BEGIN PCW(E1)←E2;PCCW(E2)←E1;END;
IF PVT(E1)=NVT(E2)∧NFACE(E1)=NFACE(E2)THEN BEGIN NCCW(E1)←E2; NCW(E2)←E1;END;
IF NVT(E1)=PVT(E2)∧PFACE(E1)=PFACE(E2)THEN BEGIN PCCW(E1)←E2; PCW(E2)←E1;END;
IF NVT(E1)=PVT(E2)∧NFACE(E1)=NFACE(E2)THEN BEGIN NCW(E1)←E2;NCCW(E2)←E1;END;
IF NVT(E1)=NVT(E2)∧PFACE(E1)=NFACE(E2)THEN BEGIN PCCW(E1)←E2; NCW(E2)←E1;END;
IF NVT(E1)=NVT(E2)∧NFACE(E1)=PFACE(E2)THEN BEGIN NCW(E1)←E2;PCCW(E2)←E1;END;
END;{λ30;W0,1260,150,1800;JUFA}
<Part Tree Routines>. As mentioned before, body nodes can be
grouped into a tree structure of parts. The parts tree consumes four
link positions (DAD, SON, BRO, SIS) and is maintained in body
nodes by the following primitives: BDET(body) detachs a body node
from the parts tree, BATT(body1,body2) attachs body1 to the ring of
children belonging to body2, and BGET(entity) returns the body node
at the head of the given face, edge or vertex ring. The SON field of a
body may contain a pointer to a headless ring of subpart bodies, the
ring of subparts is maintained in the BRO (brother) and SIS (sister)
fields, and each subpart contains a pointer back to its parent
in its DAD field. At present, the notion of a body is coincident with
the notion of a connected polyhedron; however by allowing several
bodies to be associated with a single polyhedral surface, a flexible
object such as an animal could be represented.
⊂6. Edge and Face Splitting.⊃
The most important property of the winged edge
representation is that edges and faces can be split using subroutines
that make only local alterations to the data structure; and the
splits can easily be removed (since the doubly linked rings allow
rapid deletion of nodes from a body). The edge split routine, ESPLIT,
makes a new edge and a new vertex and places them into the surface
topology as shown in Figure 3; the kill edge-vertex routine, KLEV,
undoes an ESPLIT. The face split routine, MKFE, creates a new edge
and a new face and places them into the surface topology as shown in
Figure 4; the kill face-edge routine, KLFE, undoes a MKFE.
The rest of this section concerns implementation;
the use of the split and kill
routines illustrate a pattern which applies to the coding of any
operations on winged edge structures. In a typical situation,
there are five steps: first, get the proper kinds of nodes into the
body rings using the MKF, MKE, MKV primitives; second, position the
vertices by setting their XWC, YWC, ZWC fields; third, connect each
vertex and face to one of its edges by setting face/vertex PED
fields; fourth, connect each edge to its two faces and its two
vertices by setting the NFACE, PFACE, NVT, PVT fields of the edge;
finally, set up the wing perimeter pointers by applying the WING
primitive to the pairs of edges to be mated.{Q}
{O0,0,450;L0,255;FCJC} FIGURE 3 - ESPLIT AND KLEV.{
O0,630-300,450;H4;
L0,0,0,-122;I∂2,∂2;C6; L0,0,0,122;I∂2,∂2;C6;
L-20,-160;FA}NVT{
L-20,140;FA}PVT{
L15,-7;FA}EDGE{
L-200,-12;}NFACE{
L140,-12;}PFACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-240;}BEFORE: VNEW ← ESPLIT(EDGE);{
L-200,-270;}AFTER: EDGE ← KLEV(VNEW);{
O0,630+300,450;H4;
L0,0,0,-122;I∂2,∂2;C6; L0,0,0,122;I∂2,∂2;C6;L2,2;C6;
L-20,-160;FA}NVT{
L-20,140;FA}PVT{
L15,-7;FA}VNEW{
L15,50;FA}ENEW{
L15,-75;FA}EDGE{
L-200,-12;}NFACE{
L140,-12;}PFACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-270;}BEFORE: EDGE ← KLEV(VNEW);{
L-200,-240;}AFTER: VNEW ← ESPLIT(EDGE);{
O0,630,950;
JA;I800,0;↓;λ10;F3}
INTEGER PROCEDURE ESPLIT (INTEGER EDGE);
BEGIN "ESPLIT"
INTEGER VNEW,ENEW;
COMMENT CREATE A NEW EDGE AND VERTEX;
VNEW ← MKV(PVT(EDGE));
ENEW ← MKE(EDGE);
COMMENT CONNECT VERTICES & FACES TO EDGES;
PVT(ENEW) ← PVT(EDGE);
NVT(ENEW) ← VNEW;
PVT(EDGE) ← VNEW;
PFACE(ENEW) ← PFACE(EDGE);
NFACE(ENEW) ← NFACE(EDGE);
COMMENT CONNECT EDGES TO VERTICES;
IF PED(PVT(EDGE)=EDGE THEN
PED(PVT(EDGE))←ENEW;
PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
NCW(ENEW) ← EDGE; PCCW(ENEW) ← EDGE;
PCW(EDGE) ← ENEW; PCCW(EDGE) ← ENEW;
WING(NCCW(EDGE),ENEW);
WING(PCW(EDGE),ENEW);
RETURN(VNEW);
END "ESPLIT";
{JA;↑;W620;λ10;F3}
INTEGER PROCEDURE KLEV (INTEGER VNEW);
BEGIN "KLEV"
INTEGER EDGE,ENEW,V,F,B;
ENEW ← PED(VNEW);
EDGE ← ECCW(ENEW,VNEW);
COMMENT ORIENT EDGES AS IN DIAGRAM;
IF NVT(ENEW) ≠ VNEW THEN INVERT(ENEW);
IF PVT(EDGE) ≠ VNEW THEN INVERT(EDGE);
COMMENT TIE E TO ITS NEW UPPER VERTEX AND WINGS;
V ← PVT(EDGE) ← PVT(ENEW);
WING(PCW(ENEW),EDGE);
WING(NCCW(ENEW),EDGE);
COMMENT ELIMINATE OCCURRENCES OF ENEW IN F AND V;
IF PED(V)=ENEW THEN PED(V) ← EDGE
IF PED(PFACE(EDGE))=ENEW THEN
PED(PFACE(EDGE))←EDGE;
IF PED(NFACE(EDGE))=ENEW THEN
PED(NFACE(EDGE))←EDGE;
COMMENT REMOVE NODES FROM RINGS AND RETURN EDGE;
KLV(VNEW);
KLE(ENEW);
RETURN(EDGE);
END "KLEV";
{W0,1260;λ30;JUFA}
The actual routines differ slightly from those given above in
that they do argument type checking and data structure checking;
nevertheless, a diagnostic trace of the implemented version reveals
that the ESPLIT routine executes an average of 170 PDP-10 instructions
and the KLEV routine executes an average of 200 instructions.
{O0,630,450;L0,255;FCJC} FIGURE 4 - MKFE AND KLFE.{
O0,630-300,450;H4;L2,-120;C6;L2,124;C6;
L-15,-160;FA}V2{
L-15,140;FA}V1{
L-20,-7;FA}FACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-240;}BEFORE: ENEW ← MKFE(V1,FACE,V2);{
L-200,-270;}AFTER: FACE ← KLFE(ENEW);{
O0,630+300,450;H4;
L0,0,0,-122;I∂2,∂2;C6;L0,0,0,122;I∂2,∂2;C6;
L-15,-160;FA}V2{
L-15,140;FA}V1{
L-20,-190;FA}NVT{
L-20,170;FA}PVT{
L15,-7;FA}ENEW{
L-200,15;}NFACE{
L-200,-25;}FNEW{
L140,15;}PFACE{
L140,-25;}FACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-270;}BEFORE: FACE ← KLFE(ENEW);{
L-200,-240;}AFTER: ENEW ← MKFE(V1,FACE,V2);{
O0,630,950;JA;λ10;I800,0;↓;F3}
INTEGER PROCEDURE MKFE(INTEGER V1,FACE,V2);
BEGIN "MKFE"
INTEGER V1,V2,FNEW,ENEW,E,E0,B,V;
COMMENT CREATE NEW FACE & EDGE;
FNEW ← MKF(FACE); ENEW ← MKE(PED(FACE));
COMMENT LINK NEW EDGES TO ITS FACES & VERTICES;
PED(F) ← PED(FNEW) ← ENEW;
PFACE(ENEW) ← F; NFACE(ENEW) ← FNEW;
PVT(ENEW) ← V1; NVT(ENEW) ← V2;
COMMENT GET THE WINGS OF THE NEW EDGE;
E2 ← PED(V1);
DO E2←ECW((E1←E2),V1) UNTIL FCW(E1,V1)=FACE;
E4 ← PED(V1);
DO E4←ECW((E3←E4),V2) UNTIL FCW(E3,V2)=FACE;
COMMENT SCAN CCW FROM V1 REPLACING F'S WITH FNEW;
E ← E2;
DO IF PFACE(E)=FACE THEN PFACE(E)←FNEW
ELSE NFACE(E)←FNEW;
UNTIL E4 = (E←ECCW(E,FNEW));
COMMENT LINK THE WINGS;
WING(E1,ENEW); WING(E2,ENEW);
WING(E3,ENEW); WING(E4,ENEW);
RETURN(ENEW);
END;
{JA;↑;W635;λ10;F3}
INTEGER PROCEDURE KLFE (INTEGER ENEW);
BEGIN "KLFE"
INTEGER FNEW,FACE,V1,V2,E,E1,E2,E3,E4;
COMMENT PICKUP ALL THE LINKS OF ENEW;
FACE ← PFACE(ENEW); FNEW ← NFACE(ENEW);
V1 ← PVT(ENEW); V2 ← NVT(ENEW);
E1 ← PCW(ENEW); E2 ← NCCW(ENEW);
E3 ← NCW(ENEW); E4 ← PCCW(ENEW);
COMMENT GET ENEW LINKS OUT OF FACE, V1 AND V2;
IF PED(V1) = ENEW THEN PED(V1) ← E1;
IF PED(V2) = ENEW THEN PED(V2) ← E3;
IF PED(FACE)=ENEW THEN PED(FACE)←E3;
COMMENT GET RID OF FNEW APPEARANCES;
E ← E2;
DO IF PFACE(E)=FNEW THEN PFACE(E)←FACE
ELSE NFACE(E)←FACE;
UNTIL E4 = (E←ECCW(E,FNEW));
COMMENT LINK WINGS TOGETHER ABOUT FACE;
WING(E2,E1);WING(E4,E3);
KLF(FNEW);KLE(ENEW);
RETURN(FACE);
END;
{W0,1260,0,1900;λ30;JUFA}
Again, the actual routines differ from those given above in that
they do argument type checking and data structure checking. The above two routines
typically take about twice as long to execute as the previous pair; notice
that the execution time is dependent on the length of face perimeters,
which are mostly three or four edges long.{W0,1260,0,1900;
7. Conclusion.
The narrow technical point of this paper is that a polyhedral
representation with a coherent easy to change topology can be
constructed. The larger philosophical point is that computer vision
perhaps can be realized by using computer graphics techniques to keep
an internal mental simulation in sync with the of the external
physical reality.
{⊂C;I40,0;P15;FCJC} FIGURE 6 - HIGH HORSE SILHOUETTE CONE INTERSECTION
{W0,850,0,1900;I512,550;*HH1.VID;W0,1260;
X0.380;H2;I144+80,1066;*HHSIL.1;I∂288,∂0;*HHSIL.2;I∂288,∂0;*HHSIL.3;
I1210,630;X0.66;H2;*HHSCI.4;
I1500,0;λ10;}
⊂8. References.⊃
{JUFA}
Baumgart (1974)
\Bruce G. Baumgart;
"Geometric Modeling for Computer Vision";
Stanford Artificial Intelligence Laboratory, Memo no. AIM-249,
Stanford University, October 1974.
Knuth (1968)
\Donald Ervin Knuth; ~The Art of Computer Programming~;
Addison-Wesley; Reading,Massachusetts; 1968.
Newman and Sproull (1973)
\William M. Newman and Robert F. Sproull;
~Principles of Interactive Computer Graphics~;
McGraw-Hill; New York, NY; 1973.